#include "tree_2_4.h"
#include <iostream>
#include <string>

using namespace std;

InnerNode::InnerNode ( InnerNode *parent, Node *leftPointer, int leftId, Node *rightPointer, int rightId, Tree_2_4 *tree) : Node ( parent , tree, 
false)
{
	pointers[0] = leftPointer;
	pointers[1] = rightPointer;
	studentIds[0] = leftId;
	studentIds[1] = rightId;

	count = 2;
}


void InnerNode::UpdateChildrenParent ( void )
{
	int i;

	/* .... ... .. ...... ... ...... .. ........
	 *.. ..... .... ..... ... ....., ..... .... .. split
	 *...... .... .. ....... .. ....... ..... ... ......
	 *.... .. ........ ... ...... ... ... ........ ..... ... 
	 *..... .. .......
	 */
	 

	for ( i = 0; i < count; i++ )
	{
		Node *child = (Node *) pointers[i];
		child->SetParent ( this );
	}
}

void InnerNode::Insert ( int studentId, Lesson data )
{
	int i;

	/*....... ......... .... ..... ... ...... .. ..... .. .........
	 *.. .. ......... id ..... ......... ... ...... ... ......
	 *... ...... ... ..... ......
	 *...... ..... .. .... ..... .. .. .......
	 */

	if ( studentId <= studentIds[0] )
	{
			Node *node = ( Node * ) pointers[0];
			node->Insert ( studentId, data );		

			return;
	}
	else
	{
		for ( i = 0; i < count - 1; i++ )
		{
			if ( studentId > studentIds[i] && studentId <= studentIds[i + 1] )
			{
				Node *node = ( Node * ) pointers[i + 1];
				node->Insert ( studentId, data );

				return;
			}
		}

		Node *node = ( Node * ) pointers[count - 1];
		node->Insert ( studentId, data );
	}
}

void InnerNode::Insert ( int studentId, Node *pointer )
{
	if ( this->Has ( studentId ) )
	{
		/*.. ..... . ...... ........ ... .. id ... ......., 
		 *........ ... ...... ... ....... ..... .... ..... ........
		 *... ........ ........ ... ...... .. ...... .. ....... . .......
		 *... ........
		 */

		int i;

		i = this->Find ( studentId );
		pointers[i] = pointer;

		return;
	}
	else if ( this->IsFull() )
	{	
		InnerNode *newNode = new InnerNode ( this->parent, tree );
		
		this->Split ( newNode, studentId, pointer );

		if ( this->HasParent() )
		{
			/*.. ....... ...... ... ...... ... ... .... ........ .....
			 *... ... ......, ... ............ ... ..... ... .......... 
			 *... ... .........
			 */

			parent->Insert ( newNode->Max(), newNode );
			parent->Insert ( this->Max(), this );
		}
		else
		{
			/*...... .. ... ....... ......, ........ ... ......
			 *.. ........... ... ......... .... ... .....
			 *.......... ...... .. ........ .. Max ids ... ... ......
			 *... ... ....... ... ........ .. .....
			 */

			tree->NewRoot ( this, this->Max(), newNode, newNode->Max() );
			this->parent = ( InnerNode *) tree->root;
			newNode->parent = ( InnerNode *) tree->root;
		}

	}
	else
	{
		int i, j;

		/* ...... ... ..... ... ...... .. ...........
		 * .. ......... studentId ... . ....... ... .. .....
		 *... .......... .....
		 */
		
		for ( i = 0; i < count; i++ )
		{
			if ( studentId < studentIds[i] )
			{
				for ( j = count; j > i; j-- )
				{
					studentIds[j] = studentIds[j - 1];
					pointers[j] = pointers[j - 1];
				}

				studentIds[i] = studentId;
				pointers[i] = pointer;

				count++;

				return;
			}
		}

		/*.. .......... . ......... ........ ... ... .......
		 *.......... .... ... ... .... ... .... ..........
		 */

		studentIds[count] = studentId;
		pointers[count] = pointer;

		count++;

		if ( this->HasParent() )
		{
			parent->UpdateSeparator ( this, studentId );
		}

	}
}
void InnerNode::Split ( InnerNode *newNode, int studentId, Node *pointer)
{
	int i;		

	newNode->pointers[0] = pointers[2];
	pointers[2] = NULL;
	newNode->studentIds[0] = studentIds[2];
	newNode->pointers[1] = pointers[3];
	pointers[3] = NULL;
	newNode->studentIds[1] = studentIds[3];
	
	this->count = newNode->count = 2;

	/* .... .. ...... .. ... ..... .... .. ........ .... .........
	 *..... .....
	 */

	newNode->UpdateChildrenParent();

	/* ........ ... .......... ......... .... ......... ...... */

	InnerNode *insertionNode;

	studentId > this->Max() ? insertionNode = newNode : insertionNode = this;

	int j;

	/* ...... ... ..... ... ...... .. ...........
	 * .. ......... ........ ... .......... ....
	 */
		
	for ( i = 0; i < insertionNode->count; i++ )
	{
		if ( studentId < insertionNode->studentIds[i] )
		{
			for ( j = insertionNode->count; j > i; j-- )
			{
				insertionNode->studentIds[j] = insertionNode->studentIds[j - 1];
				insertionNode->pointers[j] = insertionNode->pointers[j - 1];
			}

			insertionNode->studentIds[i] = studentId;
			insertionNode->pointers[i] = pointer;
			( ( Node * ) insertionNode->pointers[i] )->SetParent ( insertionNode );

			insertionNode->count++;

			return;
			}
		}

		/*.. .......... . ......... ........ ... ... .......
		 *.......... .... ... ... .... ... .... ..........
		 *........ ............ ... ......
		 */

		insertionNode->studentIds[count] = studentId;
		insertionNode->pointers[count] = pointer;
		( ( Node * ) insertionNode->pointers[count] )->SetParent ( insertionNode );
		

		insertionNode->count++;

		/*......... ... .... ........ ... ........... . .......
		 *.... ..... ... .........
		 */

		if ( insertionNode->HasParent() )
		{
			insertionNode->parent->UpdateSeparator ( insertionNode, studentId  );
		}

}

void InnerNode::UpdateSeparator ( Object *child, int studentId )
{
	int position = this->Find ( child );
	
	/* .. ........... . ....... .... ... .......
	 *........ ... .......... ... ...... .. .....
	 *.. ... ......... ....... ....
	 *.. .... . ...... ...... .. ....... ..... ... ........,
	 *...... .. ......... ... ..... ....
	 */

	if ( position != NOTFOUND)
	{

		studentIds [ position ] = studentId;

		if ( this->HasParent() && this->Max() == studentId )
		{
			parent->UpdateSeparator ( this, this->Max() );
		}
	}
}


